#include <stdio.h>
#include <stdlib.h>

typedef long HugeInt;

HugeInt
RandInt( HugeInt Low, HugeInt High )
{
    return rand( ) % ( High - Low + 1 ) + Low;
}


/* START: fig10_62.txt */
/* If Witness does not return 1, N is definitely composite */
/* Do this by computing ( A ^ i ) mod N and looking for */
/* non-trivial square roots of 1 along the way */
/* We are assuming very large numbers, so this is pseudocode */

HugeInt
Witness( HugeInt A, HugeInt i, HugeInt N )
{
    HugeInt X, Y;

    if( i == 0 )
        return 1;

    X = Witness( A, i / 2, N );
    if( X == 0 )  /* If N is recursively composite, stop */
        return 0;

    /* N is not prime if we find a non-trivial root of 1 */
    Y = ( X * X ) % N;
    if( Y == 1 && X != 1 && X != N - 1 )
        return 0;

    if( i % 2 != 0 )
        Y = ( A * Y ) % N;

    return Y;
}

/* IsPrime: Test if N >= 3 is prime using one value of A */
/* Repeat this procedure as many times as needed for */
/* desired error rate */

int
IsPrime( HugeInt N )
{
    return Witness( RandInt( 2, N - 2 ), N - 1, N ) == 1;
}
/* END */

main( )
{
    int i;

    for( i = 101; i < 200; i += 2 )
        if( IsPrime( i ) )
            printf( "%d is prime\n", i );

    return 0;
}
